package com.origin.niuke.dfs;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 字符串的全部子序列
 * 算法：回溯
 * 第一种: 递归, 两种情况, 取或不取
 * 第二种:
 * 从头开始遍历, 如果当前方法栈中的字母已被遍历过了, 就跳过
 *
 * @author yezh
 * @date 2023/2/8 21:04
 */
public class NC190 {

    public String[] generatePermutation(String s) {
        // write code here
        Set<String> ans = new HashSet<>();
        dfs(0, new StringBuilder(), s, ans);
        return ans.toArray(new String[0]);
    }

    void dfs(int k, StringBuilder cur, String s, Set<String> ans) {
        if (k == s.length()) {
            ans.add(cur.toString());
            return;
        }
        dfs(k + 1, cur, s, ans);
        cur.append(s.charAt(k));
        dfs(k + 1, cur, s, ans);
        cur.deleteCharAt(cur.length() - 1);
    }

    public String[] generatePermutation_tow(String s) {
        List<String> ans = new ArrayList<>();
        dfs(0, "", s, ans);
        return ans.toArray(new String[0]);
    }

    void dfs(int idx, String cur, String s, List<String> ans) {
        ans.add(cur);
        boolean[] visited = new boolean[26];
        for (int i = idx; i < s.length(); i++) {
            char c = s.charAt(i);
            if (visited[c - 'a']) continue;
            visited[c - 'a'] = true;
            dfs(i + 1, cur + c, s, ans);
        }

    }

}
